package Top_Interview_Questions.Array;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/14 20:26
 * <p>
 * https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
 */
public class _0041 {

    public static void main(String[] args) {
        _0041 test = new _0041();
        int[] nums = {3,4,-1,1};
        int[] nums1 = {7,8,9,11,12};
        test.firstMissingPositive1(nums1);
    }

    /**
     * 数组当做哈希表
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     */
    public int firstMissingPositive1(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                // 例如：数值 3 应该放在索引 2 的位置上
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }





    /**
     * 哈希表法
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        Set<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int i = 1; i <= len ; i++) {
            if (!hashSet.contains(i)){
                return i;
            }
        }

        return len + 1;
    }

}
